package aiingames.minimax;

import java.util.ArrayList;
import java.util.List;




public class AlphaBetaPruning {
	
	private enum Player {MIN,MAX};
	
	Player p = Player.MAX;
	
	public static final int SIZE = 4;
	
	int termCount =0;
	
	public AlphaBetaPruning(Player p) {
		this.p = p;
	}
	
	public State getAlphaBetaPruningDecision(State initial) {
		this.termCount = 0;
		long now = System.currentTimeMillis();
		double v = maxValue(initial,-1,1);
		for (Action a : initial.actions) {
			if (a.ut == v) {
				State res = getResult(initial, a);
				long then = System.currentTimeMillis(); 
				//System.out.println("terminal nodes:" + this.termCount + " calculation took: " + (then-now) + "ms");
				return res;				
			}
		}
		return null;
		
	}
	
	private double minValue(State state, double alpha, double beta) {
		if (terminalTest(state)) {
			return utility(state);
		}
		
		double ut = Double.POSITIVE_INFINITY;
		createActions(state);
		for (Action a: state.actions) {
			State tmp = getResult(state, a);
			a.ut = maxValue(tmp,alpha,beta);
			ut = Math.min(ut,a.ut );
			if (ut <= alpha) {
				return ut;
			}
			beta = Math.min(ut, beta);
		}
		
		return ut;
	}
	
	private double maxValue(State state, double alpha, double beta) {
		if (terminalTest(state)) {
			return utility(state);
		}
		createActions(state);
		double ut = Double.NEGATIVE_INFINITY;
		for (Action a: state.actions) {
			State tmp = getResult(state,a);
			a.ut = minValue(tmp,alpha,beta);
			ut = Math.max(ut, a.ut);
			if (ut >= beta) {
				return ut;
			}
			alpha = Math.max(alpha, ut);
		}
		
		return ut;
	}

	private State getResult(State s, Action a) {
		State ret = new State();
		ret.field = new int[SIZE][SIZE];
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				ret.field[i][j] = s.field[i][j];
			}
		}
		if (a.p == Player.MAX) {
			ret.field[a.col][a.row] = 1;
		} else {
			ret.field[a.col][a.row] = -1;
		}
		
		
		return ret;
	}
	
	private void createActions(State state) {
		List<Action> list = new ArrayList<Action>();
		int max = 0;
		int min = 0;
		for (int i = 0; i < SIZE; i++) {
			for (int j =0; j < SIZE; j++) {
				if (state.field[i][j] == -1) {
					min++;
				} else if (state.field[i][j] == 1) {
					max++;
				}
			}
		}
		Player p = null;
		if (max <= min) {
			p = Player.MAX;
		} else {
			p = Player.MIN;
		}
		for (int i = 0; i < SIZE; i++) {
			for (int j =0; j < SIZE; j++) {
				if (state.field[i][j] == 0) {
					Action a = new Action();
					a.p = p;
					a.col = i;
					a.row = j;
					list.add(a);
				}
			}
		}
		
		state.actions = list;
	}
	
	private int utility(State state) {
		
		
		
		if (!terminalTest(state)) {
			throw new RuntimeException("not a terminal state:\n" + state);
		} else {
			this.termCount++;
		}
		
		//columns
		for (int i = 0; i < SIZE; i++) {
			int c = 0;
			for (int j = 0; j < SIZE; j++) {
				c += state.field[i][j];
			}
			if (c == SIZE && p == Player.MAX || c == -SIZE && p == Player.MIN) {
				return 1;
			}
			if (c == -SIZE && p == Player.MAX || c == SIZE && p == Player.MIN) {
				return -1;
			}
		}
		
		//rows
		for (int j = 0; j < SIZE; j++) {
			int c = 0;
			for (int i = 0; i < SIZE; i++) {
				c += state.field[i][j];
			}
			if (c == SIZE && p == Player.MAX || c == -SIZE && p == Player.MIN) {
				return 1;
			}
			if (c == -SIZE && p == Player.MAX || c == SIZE && p == Player.MIN) {
				return -1;
			}
		}
		
		

		//diagonal
		//diagonal
		int c = 0;
		for (int i = 0; i < SIZE; i++ ) {
			c += state.field[i][i];
		}
		if (c == SIZE && p == Player.MAX || c == -SIZE && p == Player.MIN) {
			return 1;
		}
		if (c == -SIZE && p == Player.MAX || c == SIZE && p == Player.MIN) {
			return -1;
		}
		
		c=0;
		for (int i = 0; i < SIZE; i++) {
			int j = SIZE -i - 1;
			c += state.field[i][j];
		}
		if (c == SIZE && p == Player.MAX || c == -SIZE && p == Player.MIN) {
			return 1;
		}
		if (c == -SIZE && p == Player.MAX || c == SIZE && p == Player.MIN) {
			return -1;
		}
		return 0;
	}
	
	private boolean terminalTest(State state) {
		//columns
		int ones = 0;
		
		for (int i = 0; i < SIZE; i++) {
			int c = 0;
			for (int j = 0; j < SIZE; j++) {
				c += state.field[i][j];
				if (state.field[i][j] != 0) {
					ones++;
				}
			}
			if (Math.abs(c) == SIZE) {
				return true;
			}
		}
		
		if (ones == SIZE*SIZE) {
			return true;
		}

		//rows
		for (int j = 0; j < SIZE; j++) {
			int c = 0;
			for (int i = 0; i < SIZE; i++) {
				c += state.field[i][j];
			}
			if (Math.abs(c) == SIZE) {
				return true;
			}
		}
		

		//diagonal
		int c = 0;
		for (int i = 0; i < SIZE; i++ ) {
			c += state.field[i][i];
		}
		if (Math.abs(c) == SIZE) {
			return true;
		}
		
		c=0;
		for (int i = 0; i < SIZE; i++) {
			int j = SIZE -i -1;
			c += state.field[i][j];
		}
		if (Math.abs(c) == SIZE) {
			return true;
		}
		
		return false;		
	}

	private static class Action {
		int row;
		int col;
		Player p;
		double ut;
	}
	
	
	private static class State {
		public List<Action> actions;
		int [][] field = new int[SIZE][SIZE];
		
		public String toString() {
			StringBuffer buf = new StringBuffer();
			for (int i = 0; i < SIZE; i++) {
				for (int j = 0; j < SIZE; j++) {
					buf.append('|');
					if (field[i][j] == 0) {
						buf.append(' ');
					} else if (field[i][j] == 1) {
						buf.append('x');
					} else {
						buf.append('o');
					}
				}
				buf.append('|');
				buf.append('\n');
			}
			
			return buf.toString();
		}
	}

	public static void main(String  [] args) {
		State s1 = new State();
//		s1.field[0][0] = 1;
//		s1.field[2][0] = -1;
////		s1.field[2][2] = 1;
////		s1.field[1][2] = -1;
//////////		
////		s1.field[0][1] = -1;
////		s1.field[0][2] = 1;
//////		s1.field[1][2] = -1;
////		s1.field[1][0] = 1;
////		s1.field[2][0] = -1;
		AlphaBetaPruning mm1 = new AlphaBetaPruning(Player.MAX);
		AlphaBetaPruning mm2 = new AlphaBetaPruning(Player.MIN);
		int iter = 0;
		//System.out.println(s1);
		do {
			if (iter %2 == 0) {
				s1 = mm1.getAlphaBetaPruningDecision(s1);
			} else {
				s1 = mm2.getAlphaBetaPruningDecision(s1);
			}
		
				//System.out.println(s1);
				iter++;
		} while(!mm1.terminalTest(s1));
		
	}
}
